package algorithms.leecode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
public class Au131 {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        node1.neighbors = new ArrayList(){{
            add(node2);
            add(node4);
        }};
        node2.neighbors = new ArrayList(){{
            add(node1);
            add(node3);
        }};
        node3.neighbors = new ArrayList(){{
            add(node2);
            add(node4);
        }};;
        node4.neighbors = new ArrayList(){{
            add(node1);
            add(node3);
        }};
        new Au131().cloneGraph(node1);
    }

    public Node cloneGraph(Node node) {
        Node nod = dfs(node);
        System.err.println(nod);
        return nod;
    }
    Map<Integer,Node> mp = new HashMap<>();
    public Node dfs(Node node) {
        Node nd = new Node();
        nd.val = node.val;
        mp.put(nd.val,nd);
        List<Node> neighbors = new ArrayList<>();
        List<Node> ng = node.neighbors;
        for (Node n : ng) {
            if (mp.containsKey(n.val)) {
                neighbors.add(mp.get(n.val));
            } else {
                neighbors.add(dfs(n));
            }
        }
        nd.neighbors = neighbors;
        return nd;
    }
}
